package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 93. 复原IP地址
 * <p>
 * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
 * <p>
 * 示例:
 * <p>
 * 输入: "25525511135"
 * 输出: ["255.255.11.135", "255.255.111.35"]
 */
public class Test93复原IP地址 {

    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        if (s == null || s.length() < 4)
            return result;
        restoreIpAddresses(s, 0, new ArrayList<>(), result);
        return result;
    }

    /**
     * 127.0.0.1 这样的ip地址中分成4段，所以我们要把127001这样的字符串拿来解析成一段一段的
     * 若能解析成4段，且每一段都合法，那就是一个答案
     *
     * @param s      原始的ip字符串
     * @param index  本次检索ip字符串的位置，用来截取ip段
     * @param list   存储一次递归中合法的ip段
     * @param result 合法的全部IP地址
     */
    public void restoreIpAddresses(String s, int index, List<String> list, List<String> result) {
        /*
        list 里面存储的一定是是合法的ip段，最大长度只能是4，所以list要么没填满，要么满了
        (4 - list.size()) * 3 表示的是剩余没填入的IP段的最大长度
        */
        int maxLength = (4 - list.size()) * 3;
        // 如果原字符串剩余字符 大于预期最大长度 不符合要求
        /*
        s.length() - index 表示的是剩余的没检索的字符串的长度
        它应该小于等于 maxLength

        你想：直到 index 处，前面的字符全部被检索了，也全部填入到 list 里面去了
        那么 index 后面的字符会接着被填入到 list 里面，但是 list 里面最多只能容纳 maxLength 个字符了
        若是index后面的字符长度大于了这个 maxLength，则无法继续处理
         */
        if (s.length() - index > maxLength) {
            return;
        }
        // 满足条件
        if (list.size() == 4 && s.length() == index) {
            // 拼接处结果
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < list.size(); i++) {
                if (i == 0)
                    sb.append(list.get(i));
                else
                    sb.append(".").append(list.get(i));
            }
            result.add(sb.toString());
        }
        // 遍历整个ip字符串s，每次截取合法的ip段并存入list中，一旦遇到无法获取合法ip段的情况就回溯
        for (int i = index + 1; i <= index + 3 && i <= s.length(); i++) {
            String ip = s.substring(index, i);  // 左闭右开区间，例如 [0, 3) 将获得一个IP段
            // 大于 255 不符合 ip 规则
            if (Integer.parseInt(ip) > 255)
                continue;
            // 大于1位数时 0不能为头
            if (ip.length() > 1 && "0".equals(ip.substring(0, 1)))
                continue;
            list.add(ip);
            restoreIpAddresses(s, i, list, result);
            list.remove(list.size() - 1);
        }
    }

    public static void main(String[] args) {

    }
}
